home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / std / c++ / 199 < prev    next >
Encoding:
Text File  |  1996-08-06  |  11.0 KB  |  280 lines

  1. Path: engnews1.Eng.Sun.COM!taumet!clamage
  2. From: kanze@lts.sel.alcatel.de (James Kanze US/ESC 60/3/141 #40763)
  3. Newsgroups: comp.std.c++
  4. Subject: Re: Guarantees concerning references/pointers into string
  5. Date: 31 Jan 1996 17:39:43 GMT
  6. Organization: SEL
  7. Sender: news@lts.sel.alcatel.de
  8. Approved: clamage@eng.sun.com (comp.std.c++)
  9. Message-ID: <KANZE.96Jan31183659@slsvewt.lts.sel.alcatel.de>
  10. References: <KANZE.96Jan25184235@gabi.gabi-soft.fr> <310BF7E7.4DDE@suphys.physics.su.oz.au>
  11. NNTP-Posting-Host: taumet.eng.sun.com
  12. Content-Type: text
  13. In-Reply-To: John Max Skaller's message of 28 Jan 1996 23:24:34 GMT
  14. Apparently-To: std-c++@ncar.ucar.edu
  15. Content-Length: 10298
  16. X-Lines: 256
  17. Originator: clamage@taumet
  18.  
  19. In article <310BF7E7.4DDE@suphys.physics.su.oz.au> John Max Skaller
  20. <maxtal@suphys.physics.su.oz.au> writes:
  21.  
  22. |> J. Kanze wrote:
  23.  
  24. |> >         a = "A lot of junk" ;
  25. |> >         a.reserve( 100 ) ;
  26. |> >         char*               p1 = &a[ 1 ] ;
  27. |> >         //  b = a ;
  28. |> >         a.insert( 6 , "---" ) ;
  29. |> >         char*               p2 = &a[ 1 ] ;
  30. |> >         cout << "Reserve test: " << (p1 == p2 ? "Passed" : "Failed") << endl ;
  31. |> > 
  32. |> > As I interpret the standard, the above is required to work.
  33.  
  34. |>     I agree. It should work.
  35.  
  36.  
  37. |> > The presense of
  38. |> > `reserve' makes copy on write anything but trivial to implement
  39. |> > correctly.  (The exact case above is actually easy to avoid, and I'm
  40. |> > surprised that g++ has the error.  But try uncommenting the assignment
  41. |> > in the above code, and it becomes considerably more difficult to avoid
  42. |> > the problem.)
  43.  
  44. |>     I do NOT understand. There is a problem with
  45. |> copy on write implementations, but it has nothing to do with
  46. |> reserve(). Rather, the problem occurs because of aliasing:
  47.  
  48. It involves reserve, because reserve implicitly guarantees that your
  49. pointers remain value despite following write operations.  At least,
  50. that is my somewhat shaky interpretation of the current draft, and a
  51. major part of my question was: is this interpretation valid?
  52.  
  53. Without the reserve, I do *not* expect the above to work.
  54.  
  55. |>     void f(string &x, string const &y) {
  56. |>         char &ch = y[0];
  57. |>         x = "fred";
  58. |>     }
  59.  
  60. |> Is "ch" assured? Nope:
  61.  
  62. |>     string s = "Hi";
  63. |>     f(s,s);
  64.  
  65.  
  66. |> Consider now:
  67.  
  68. |>     void f(string &x, string const &y) {
  69. |>         char &ch = y[0];
  70. |>         cout << x[0] << ch;
  71. |>     }
  72.  
  73. |> Here, ch might _still_ be invalidated even though there
  74. |> is no write operation -- merely binding a non-const
  75. |> lvalue into the string _potentially_ allows writing,
  76. |> and the string class has no choice but to do the copy
  77. |> immediately. C++ overloads on the constness of the object
  78. |> and not whether the context is an lvalue or rvalue context.
  79.  
  80. Agreed.  This was the whole point of my question.
  81.  
  82. As I understand the current draft (and I'm not sure about my
  83. interpretation), pointers and references into a string are valid until
  84. `reallocation occurs'.  The draft makes very few statements with
  85. regards to this; I see nothing off hand that would prevent
  86. reallocation even when calling a const function (e.g. c_str, for
  87. example).
  88.  
  89. The draft does guarantee (or I think it does) that after a call to
  90. reserve, *no* reallocation will take place until the string becomes
  91. bigger than the reserved size.  (The actual wording refers to
  92. insertion making the string bigger.  This seems very vague to me.)  In
  93. practical terms, this means that 1) the copy must be made unique in
  94. reserve, if it isn't already, and 2) no other string object may be
  95. made to refer to this copy, since that could trigger a reallocation on
  96. writing.  Implementing 2 is not trivial, or at least, I didn't find a
  97. non-trivial way of doing it.
  98.  
  99. |> > One further question occurs: when may reallocation (and the resulting
  100. |> > invalidation of the pointers) occur when reserve has not been called?
  101. |> > For example, is the following guaranteed to work as expected:
  102. |> > 
  103. |> >     string              s ;
  104. |> >     size_t              i , j ;
  105. |> >     assert( i < s.size() , j < s.size() ) ;
  106. |> >     s[ i ] = s[ j ] ;
  107.  
  108. |> > I would like for the last statement to be well defined, but according to
  109. |> > my reading of the standard, it isn't.  Reallocation is allowed in the
  110. |> > non-const version of operator[] (and must be, if copy on write is to be
  111. |> > a legal implementation).  
  112.  
  113. |>     "must be" doesn't follow -- indexing _could_ return
  114. |> a proxy object rather than a reference, couldn't it?
  115.  
  116. Not according to the September draft.  (IMHO, this is just a careless
  117. error.  The return type should be implementation defined.)
  118.  
  119. |> > This operator is called twice in the
  120. |> > expression, and the compiler could very easily (and legally) generate
  121. |> > both calls before using either of the results.  But if the second call
  122. |> > reallocates, the reference returned by the first call is invalidated.
  123. |> > (I cannot actually conceive of an implementation in which the second
  124. |> > call reallocates, but I cannot find anything in the draft to guarantee
  125. |> > that it won't.)
  126.  
  127. |> A naive COW implementation in which the "first" evaluated index operator 
  128. |> is the RHS above and for which a const alias is used will 
  129. |> invoke the CONST indexing operator, while evaluating 
  130. |> the LHS invokes the NONCONST indexing operator and triggers 
  131. |> reallocation. For example:
  132.  
  133. |>     string s = "Hello";
  134. |>     string const &cs = s;
  135. |>     s[0] = cs[0];
  136.  
  137. |> is almost certain to fail in a naive COW implementation
  138. |> if the RHS indexing happens to return a lvalue instead 
  139. |> of an rvalue. 
  140.  
  141. Correct.
  142.  
  143. |> Here's another case:
  144.  
  145. |>     s.insert(const_iterator, "x");
  146.  
  147. |> [No, there's nothing wrong with inserting at a const iterator.
  148. |> It is the string object before the dot (.) that must be
  149. |> non-const to support insertion, NOT the iterator, which merely
  150. |> marks the place where the insertion is to occur.]
  151. |> But calling the "insert" method might trigger a reallocation.
  152.  
  153. |> I would not be surprised at an implemention
  154. |> which split the representation when ANY iterator 
  155. |> was got from the string -- const or not. The same
  156. |> fix can be applied to indexing (requiring a mutable
  157. |> pointer inside the string object).
  158.  
  159. But it doesn't help.  Consider the following:
  160.  
  161.     string          s1 , s2 ;
  162.     char*           pc( &s1[ i ] ) ;
  163.                     //  At this point, s1 representation
  164.                     //  is unique.
  165.     s2 = s1 ;            //  And now it is not.
  166.     assert( pc == &s1[ i ] ) ;
  167.  
  168. As far as I can tell, most COW will probably fail the above assertion
  169. because of the potential write through the results of the non-const
  170. operator[] in the assert.  I don't think a proxy will help; if the
  171. above is to be defined in a logical manner, the proxy will have to
  172. overload operator&, and the implementation of this will inevitably
  173. trigger a split of the two representations.
  174.  
  175. Again, as far as I can tell, an implementation in which this will fail
  176. is *NOT* forbidden by the draft.  Add a call to s1.reserve() before
  177. the first address, however, and I believe that it must work (or
  178. reserve has no real semantics, and is just a hint).  Let's face it,
  179. I've not modified the s1 at all.
  180.  
  181. |> Is there a rule for writing COW that makes it work???
  182.  
  183. |> Yes. IF any method returns something that
  184. |> binds directly to the representation, it must
  185. |> be split BEFORE the binding is done.
  186.  
  187. It doesn't help.  You also have to remember that you don't have the
  188. right to share the representation in a later assignment.
  189.  
  190. |> For example, if the indexing operator uses
  191. |> a suitable proxy, there's no problem.
  192. |> Similarly, if the iterators are pairs:
  193.  
  194. |>     (string*, index)
  195.  
  196. |> there's no problem. 
  197.  
  198. As long as you don't actually modify the string.  But consider the
  199. following:
  200.  
  201.     string          s1 , s2 ;
  202.     s1 = "123" ;
  203.     char const*     pc( &s1[ 1 ] ) ;
  204.     s2 = s1 ;            //  Share the image
  205.     s1[ 0 ] = 'a' ;            //  And the value in pc?
  206.  
  207. In my own string (before the ISO class), I simply didn't support
  208. non-const indexing for the longest time.  And in practice, I never
  209. found that to be a restriction.  (Strings are not containers, and the
  210. semantic value of the individual characters depends on the context of
  211. the string.)  When I finally added non-const indexing (user demand), I
  212. used a proxy class much like what you suggest, and I didn't support
  213. taking the address.
  214.  
  215. In my implementation of the ISO basic_string class, I added a
  216. guarantee that no non-const function will invalidate pointers.  My
  217. implementation also maintains the guarantee concerning pointers after
  218. a reserve; *no* operation on that string will invalidate pointers as
  219. long as the resulting string will fit into the capacity().  This
  220. latter guarantee required some fairly complex handling, however, and
  221. has a definite negative impact on run-time.
  222.  
  223. |> My current string class MTLstring does the latter AND is a naive 
  224. |> (non-COW) implementation AND allows accesses
  225. |> "off the end" -- it is highly robust, and VERY hard to break 
  226. |> without doing "obvious" things (like deleting the string).
  227. |> It permits you to insert or erase in the string
  228. |> and will NOT invalidate any iterators. In fact,
  229. |> my iterators CANNOT be invalidated except by deleting
  230. |> the string. They may, of course, magically point to
  231. |> a new character after an insertion. [In fact,
  232. |> my iterators can be anchored at EITHER end of the
  233. |> string, so a "end()-1" iterator is NOT moved
  234. |> by an insertion at end()-2, because it's anchored
  235. |> to the RHS end of the string, not the LHS end.]
  236.  
  237. I did it even simpler.  My string class initially had *no* non-const
  238. functions other than assign, and no way of getting an internal address
  239. of the string.  Very quickly, I found that I needed the equivalent of
  240. c_str(), but for a long time, that was the only compromise.
  241.  
  242. |> The price is inefficiency: read/write can
  243. |> be made very efficient by grabbing a pointer
  244. |> to the raw array, but duplicate copying
  245. |> make the class unsuitable for som applications.
  246.  
  247. |> But I'm just not interested in chasing the kind of 
  248. |> horrible problems that fragile implementations have, in a class
  249. |> I personally conceive as a formatting
  250. |> and message passing utility.
  251.  
  252. I agree here.  My string class was never written with performance in
  253. mind, simply because my programs are not string oriented.  The one
  254. exception is a program to format comments; all of the formatting is
  255. done with my string class.  But how many lines will a comment have,
  256. anyway.
  257.  
  258. |> A reasonable compromise for a COW implementation
  259. |> to make users of the indexing operators
  260. |> and STL iterators pay for using non-OO syntax:
  261.  
  262. |>     s.put(index, chr)
  263.  
  264. |> does not suffer from these problems, for example.
  265.  
  266. See above.  If you allow external pointers, and you guarantee that the
  267. above will not invalidate them (in general, or because of an explicit
  268. request from the user, like reserve), then you have a problem.
  269. --
  270. James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
  271. GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
  272. Conseils, Θtudes et rΘalisations en logiciel orientΘ objet --
  273.                 -- A la recherche d'une activitΘ dans une region francophone
  274.  
  275.  
  276. [ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  277.   Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  278.   is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]
  279.  
  280.